/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/minimum-adjustment-cost
   @Language: C++
   @Datetime: 16-02-09 08:18
   */

class Solution {
public:
	/*
	 * @param A: An integer array
	 * @param target: An integer
	 * @return: An integer
	 */
	int MinAdjustmentCost(vector<int> &A, int target) {
		// write your code here
		int n=A.size(), cost=INT_MAX;
		vector<vector<int> > dp(n+1,vector<int>(101,INT_MAX));
		dp[0]=vector<int>(101,0);
		for(int i=1; i<=n; ++i){
			for(int j=0; j<101; ++j){
				int diff=abs(A[i-1]-j), start=max(j-target,0), end=min(j+target,100);
				// abs(j-k)<=target
				for(int k=start; k<=end; ++k)
					dp[i][j]=min(dp[i][j],dp[i-1][k]+diff);
			}
		}
		for(int i=1; i<101; ++i)
			cost=cost<dp[n][i]?cost:dp[n][i];
		return cost;
	}
};
